package com.liunian.algorithmstudy.tree;

public class ConvertBST538 extends TreeNode {

	/**
	 给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
	 使每个节点node的新值等于原树中大于或等于 node.val 的值之和。

	 提醒一下，二叉搜索树满足下列约束条件：

	 节点的左子树仅包含键 小于 节点键的节点。
	 节点的右子树仅包含键 大于 节点键的节点。
	 左右子树也必须是二叉搜索树。
	 注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
	 */
	int record = 0;
	public TreeNode convertBST(TreeNode root) {
		if (root == null) {
			return null;
		}
		TreeNode rightTree = convertBST(root.right);
		record += root.val;
		root.val = record;
		TreeNode leftTree = convertBST(root.left);
		root.left = leftTree;
		root.right = rightTree;
		return root;
	}

}
